package lc;

import org.junit.Test;

public class Ex134 {
    class Solution {
        public int canCompleteCircuit(int[] gas, int[] cost) {
            int n = cost.length;
            for (int i = 0; i < n; i++) {
                int cur = 0;
                int idx = i;
                while (true) {
                    if (cur + gas[idx] < cost[idx]) {
                        break;
                    }
                    cur = cur + gas[idx] - cost[idx];
                    idx = (idx + 1) % n;
                    if (idx == i) return i;
                }
            }
            return -1;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        // int[] gas = new int[]{2,3,4}, cost = {3,4,3};
        int[] gas = new int[]{1,2,3,4,5}, cost = {3,4,5, 1, 2};

        System.out.println(s.canCompleteCircuit(gas, cost));
    }
}
